package 数据结构与算法分析_书;

import java.util.Comparator;
import java.util.stream.IntStream;

/*
    书 1.1
 */
public class K_maximum_value {
    public static void main(String[] args) {
        int[] arr = new int[]{0,2,4,1,4,56,7,2,3,56,6,422,3};
        System.out.println(findKth(arr, 1));
    }

    /**
     * 查询第 k 个最大值
     * 思路：新建大小为k的数组，读取前k个数据进入数组，倒序排列，然后逐个读入，并排序，每次挤出一个元素，最后返回第k个元素
     *
     * @param arr 源数组
     * @param k   位置
     * @return 第 k 个最大值
     */
    private static int findKth(int[] arr, int k) {
        //1.新建大小为K的数组
        int[] temp = new int[k];
        //2.读取前k个元素
        for (int i = 0; i < k; i++) {
            temp[i] = arr[i];
        }
        //3.倒序排列
        temp = IntStream.of(temp)
                .boxed()
                .sorted(Comparator.reverseOrder())
                .mapToInt(Integer::intValue)
                .toArray();
        //4.逐个读入元素，并排序
        for (int i = k; i < arr.length; i++) {
            int t = arr[i];
            if (t < temp[k - 1]) {
                continue;
            }
            //找位置
            int index = locateIndex(temp, t);
            //挤元素
            for (int j = index; j < temp.length; j++) {
                int element = temp[j];
                temp[j] = t;
                if (j + 1 < temp.length) {
                    t = temp[j + 1];
                    temp[j + 1] = element;
                }
            }
        }
        return temp[k - 1];
    }

    /**
     * 折半查找
     * @param arr 倒序数组
     * @param num 新元素
     * @return 返回插入的下标
     */
    private static int locateIndex(int[] arr, int num) {
        int p1 = 0;
        int p2 = arr.length - 1;
        while (p1 <= p2) {
            int middle = (p1 + p2) / 2;
            if (num > arr[middle]) {
                if (middle == 0 || num < arr[middle - 1]) {
                    return middle;
                }
                p2 = middle - 1;
            } else if (num < arr[middle]) {
                if (middle == arr.length - 1) {
                    return middle;
                } else if (num > arr[middle + 1]){
                    return middle + 1;
                }
                p1 = middle + 1;
            } else {
                return middle + 1;
            }
        }
        return -1;
    }
}
